package leetcode_401_500;

import javax.sound.midi.Soundbank;
import java.util.HashSet;
import java.util.Set;

public class LeeCode_457 {
    public static void main(String[] args) {
//        System.out.println(circularArrayLoop(new int[]{2, -1, 1, 2, 2}));
//        System.out.println(circularArrayLoop(new int[]{-1, 2}));
        System.out.println(circularArrayLoop(new int[]{-2,1,-1,-2,-2}));
        System.out.println(circularArrayLoop(new int[]{-1, -2, -3, -4, -5}));
        System.out.println(circularArrayLoop(new int[]{1,1,2}));
    }
    private static boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        Set<Integer> used = new HashSet<>();
        int tmp = n * n;
        for (int i = 0; i < n; i++) {
            if (used.contains(i)){
                continue;
            }
            boolean flag = nums[i] > 0;
            boolean f = true;
            int iNum = tmp + i, pre = -1;
            int index = iNum % n;
            Set<Integer> now = new HashSet<>();
            now.add(i);
            while (true){
                iNum += nums[index];
                pre = index;
                index = iNum % n;
                used.add(index);
                if ((flag && nums[index] < 0) || (!flag && nums[index] > 0)){
                    f = false;
                    break;
                }
                if (now.contains(index)){
                    if (index == pre){
                        f = false;
                    }
                    break;
                }
                now.add(index);
            }
            if (f)
                return true;
        }
        return false;
    }
}
